SRM 668

Match Summary

Round Overview
Discuss this match

VerySecureEncryption

This is an implementation problem. Just do as the problem says and rearrange the letters according to the key exactly K times.

A hard part is to interpret how the rearrangement works. For each i, the letter originally in position ‘key’[i] should be in position i after the rearrangement.

newmessage[i] = message[ key[i] ]

It helps to rearrange in a new copy of the message. C++ code follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
string encrypt(string message, vector < int > key, int K) {
  // repeat K times:
  for (int i = 0; i < K; i++) {
    // initialize a new string:
    string newm(message.size(), '-');
    // rearrange
    for (int j = 0; j < key.size(); j++) {
      newm[key[j]] = message[j];
    }
    // save new string as new message
    message = newm;
  }
  return message;
}

String manipulation in other languages is different. In Java and python, for example you cannot modify a string object. You can use an auxiliary character array for the temporary message instead:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class VerySecureEncryption {
  public String encrypt(String message, int[] key, int K) {

    // repeat K times:
    for (int i = 0; i < K; i++) {
      // initiallize a char array:
      char[] newm = new char[message.length()];
      // rearrange
      for (int j = 0; j < key.length; j++) {
        newm[key[j]] = message.charAt(j);
      }
      // save new string as new message, convert the char array to String
      message = new String(newm);
    }
    return message;
  }

IsItASquare

The input points might be in any order. There are 4! = 120 different orders for the points. We can just try them all. Imagine that what we want is a square with vertices A, B, C and D.

A___B
|       |
|____|
C    D

The square may be rotated in who knows what ways. But something universal about a correct square regardless of the rotations is the relationship between distances of its vertices. bar(AB), bar(BD), bar(DC), bar(AC) must be equal. We can find the distances by using the Euclidean distance. Note that the Euclidean distance is the square root of an addition. In the case of integer coordinates, the square of the Euclidean distance will always be a integer. When comparing these distances, they will all be square roots of a integer. If you want to know if sqrt(x) = sqrt(y) then you can just compare x = y. Comparing integers is more reliable than comparing floating point values, specially when the result we look after is a discrete value (e.g a Yes or No question). So we can compare: bar(AB)^2 = bar(AC)^2 = bar(BC)^2 = bar(CD)^2.

The square is not the only 4-sided polygon in which all sides are equal. There is also the Rhombus. The above condition is true both for squares and Rhombuses. We need more conditions. The diagonals, bar(AD) and bar(BC) must also be equal. So we should also check for: bar(AD)^2 = bar(BC)^2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Finds the square of the Euclidean distance between two points
// (Euclidean distance formula without the square root)
int euclid2(int x0, int y0, int x1, int y1) {
  int dx = x0 - x1;
  int dy = y0 - y1;
  return dx * dx + dy * dy;
}

string isSquare(vector < int > x, vector < int > y) {

  // find an assigment of the order of the 4 points
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++)
      if (b != a) {
        for (int c = 0; c < 4; c++)
          if ((b != c) && (c != a)) {
            // d should be the remaining point:
            int d = 0;
            while ((a == d) || (b == d) || (c == d)) {
              d++;
            }
            int ab = euclid2(x[a], y[a], x[b], y[b]);
            int ac = euclid2(x[a], y[a], x[c], y[c]);
            int bd = euclid2(x[d], y[d], x[b], y[b]);
            int cd = euclid2(x[d], y[d], x[c], y[c]);

            int ad = euclid2(x[a], y[a], x[d], y[d]);
            int bc = euclid2(x[c], y[c], x[b], y[b]);

            if ((ab == ac) && (ac == bd) && (bd == cd) && (ad == bc)) {
              return "It's a square";
            }

          }
      }
  }
  return "Not a square";
}

AnArray

We can reinterpret the problem as counting the number of ways to pick 3 elements of the array such that their product is a multiple of K. An O(n^3) approach would be too much for the constraints so we should look for something different.

A recursive step

Imagine we pick the first element x that will be part of the product. What is needed of the other elements y and z? For now let’s take the remaining part of the product y*z as a single entity w. We want x * w to be a multiple of K. E.g: Imagine x = 10 and K = 14, we can tell that w must be a multiple of 7 for this to work. If w is a multiple of 7, when multiplied by 10 it’s like multiplying by 2 and then by 5. When multiplying a multiple of 7 by 2, we will get a multiple of 14. How to do this in the general way? x will already be a multiple of some divisor of K, even if they are coprime the common divisor will be 1. So let’s use the greatest common divisor of x and K: g = “gcd”(x, K), w needs to be a multiple of x / g.

Dynamic Programming

We’ve reached a more general version of the problem: Given an array with n elements, pick t elements such that their product is a multiple of d. f(n,t,d) is a function that counts the number of ways to do that.

Normally we can decide what to do with element A[n-1], after this we can consider the same problem using only the first n-1 elements.

• If we include A[n-1] in the group of picked elements. Then we need the remaining product needs to be a multiple of d / (“gcd”(A[n-1], d)) and we’d only need to pick t-1 more elements: f(n-1, t-1, d // “gcd”(A[n-1], d) ) is the number of ways when we decide to include A[n-1].

• Not including A[n-1] the number of elements to pick remains t and they need to still make a multiple of d when multiplied: f(n-1, t, d).

There are base cases when n = 0 and t = 0. When t = 0, there is nothing more to add, we hope d = 1, in that case the result is 1, it is valid because anything is a multiple of 1. Else the result is 0. When n = 0 and t != 1, there are not enough elements from which to pick and the result is 0.

Let’s talk about complexity. For each possible value of d, there are (n+1) * 4 possible states. The values of d all come from dividing a previous d by one of its divisors and the first value used is K. All valid values of d are divisors of K. Given the constraints, what is the maximum possible number of distinct divisors of K? A useful thing to remember for when we need an upper bound in the number of divisors is the concept of highly composite numbers. The worst highly composite number smaller than 10^8 has 768 divisors, that is our upper bound. So the maximum number of states is 2001 * 4 * 768. If we implement the recurrence using memoization or iterative dynamic programming, it should run in time because each state needs O(1) time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int K;
vector < int > A;

// use an associative array, this time a c++ std::map, this is because the 
// divisors of K are a small group but each member can be very high so using 
// a simple array wouldn't be possible.
// this adds an O(log(divisors(K))) factor, however.
map < int, int > dp[2001][4];

int gcd(int a, int b) {
  //Euclid's algorithm
  while (b != 0) {
    tie(a, b) = make_tuple(b, a % b);
  }
  return a;
}

int f(int n, int t, int d) {
  // read prior memory:
  auto it = dp[n][t].find(d);
  if (it != dp[n][t].end()) {
    return it - > second;
  }
  // initialize in 0
  int res = dp[n][t][d];
  res = 0;
  if (t == 0) {
    if (d == 1) {
      res = 1;
    }
  } else if (n == 0) {
    res = 0;
  } else {
    // use it
    int g = gcd(d, A[n - 1]);
    res += f(n - 1, t - 1, d / g);

    // don't use it
    res += f(n - 1, t, d);
  }
  // save in memory
  dp[n][t][d] = res;
  return res;

}

int solveProblem(vector < int > A, int K) {
  this - > K = K;
  this - > A = A;
  return f(A.size(), 3, K);
}

PaintTheRoom

We have a W times H board and we need to visit each cell in the board exactly K times.

K = 1

The easiest case is when K=1. We just need to find a trip that visits all the cells exactly once. We can for example use a S-like pattern: First visit all the cells in the top row from left to right, then all the cells in top-second row from right to left then left to right and so and so. When K=1, the trip is always possible.

K > 1, W = 1, H = 1

When K > 1, things get harder so let’s try the simplest possible case, a 1 times 1 board. It is impossible to visit this cell more than once.

K > 1, W = 2, H = 1

Another very simple case, this time we have two adjacent cells. K = 2 is possible. Start in cell A, move to B, then A again and B again. This works for any K. A -> B - > A -> B - > A-> B - > A-> … -> B.

K > 1, W = 3, H = 1

Another impossible case.

K > 1, W = 4, H = 1

This one is interesting because imagine there were 4 cells in succession: A,B,C,D. From the 2 times 1 case, we know that there exists a route that visits the first two cells A and B exactly K times for any K, and we can make it end in B. Then we can move from B to C and start exactly the same route, this time using C and D. As a result there is a route that visits the four cells exactly K times.

The nice thing is that we can extend this logic to apply to any even W. Assume it is possible for the first W-2 cells, then repeat the 2 times 1 route for the last 2 cells.

And we can extend the logic for any height as well. After finishing a row using the above strategy, we can consume the next row using it in reverse. Similar to the S pattern we used earlier.

This means that we can solve any case with even W. Because we can just rotate the board this also means we can solve any case with even H as well.

K > 1, odd W, odd H

You can try these cases many times and it will become apparent that no case in these conditions has a solution.

Code

So the solution is to return “Paint” if K = 1 or if W or H are even.

1
2
3
4
5
6
7
string canPaintEvenly(int R, int C, int K) {
  if ((R % 2 == 0) || (C % 2 == 0) || (K == 1)) {
    return "Paint";
  } else {
    return "Cannot paint";
  }
}

WalkingToSchool

Let’s begin with alternative ways to understand the problem’s question. It’s useful to read the notes: “there exists a k-route for all sufficiently large k” is true if and only if there is some integer x such that there exists a k-route for all k greater than x. Another way to understand this is : “The number of integers k without a k-route is finite”.

Connectivity

There is an easy way to make the number of wrong k values infinite: When no path at all exists between 0 and 1 or between 1 and 0. This means that all values of k are invalid. These cases are trivial to detect so from now on we will assume that the graph is such that a path exists from 0 to 1 and from 1 to 0. This also means at least one cycle exists.

Forget the k-routes

A k-route requires a k-path between 0 and 1 AND between 1 and 0 to exist. If for integer x then all k >= xhave a k-route, this means that all k >= x have the two necessary kinds of k-paths. This means that the number of wrong k values is finite both for the 0-1 paths and the 1-0 paths. This is interesting, if the number of wrong k values is infinite for either 0-1 k-paths OR 1-0 k-paths then the number of wrong k for k-routes is also infinite. If we find that for k >= x, all k-paths from 0 to 1 were valid and for k >= y all k-paths from 1 to 0 were valid then for k >= max(x,y) all k-routes will be valid. So we can stop worrying about k-routes and just try to solve for the k-path.

The answer is the same for both k-paths

We need to answer the infinite wrong k values question for two kinds of k-paths. But remember that there is always at least one path from 0 to 1 and one path from 1 to 0. Let’s say the length of the path from 1 to 0 is w. In case there is a k-path from 0 to 1, then we can take the length w path from 1 to 0, add the k-path, then repeat the length w path again. This becomes a path from 1 to 0 of length 2w + k. Which would mean that for any k-path from 0 to 1, there is a (2w + k)-path from 1 to 0. Imagine there was an x such that for every k >= x, the k-path from 0 to 1 exists, this means that there is an y = x + 2w such that for every k >= x + 2w, a k-path from 1 to 0 exists. In other words, if the number of wrong k values is finite for 0-1, then it will also be finite for 1-0. The same is true in the other direction. So now we just need to worry about verifying for 0->1.

Cycles

This question is all about cycles. If there was no cycle at all between 0->1. Then the number of valid k would be finite, guaranteed that invalid k were infinite. But we can assume there is at least one cycle. If there was exactly one cycle, of length w, then no matter what we did, the number of invalid k would be infinite. For the cycle to be unique, then the paths between 0 and 1 and between 1 and 0 would be unique as well. If the path 0->1 was of length z, then the path 1->0 would be of length w - z. This would mean that all the valid k are z, z + w, z + 2w, z + 3w, … Since w is at least 2, this means that invalid k are infinite: z + 1, z + w + 1, z + 2w + 1, … are all invalid.

So the solution is based around cycles, the general graph can include various cycles at distinct positions. Some cycles will not matter, however. If the cycle is not connected to 0 or 1, then it cannot be part of the k-path. All nodes in the cycle have to be reachable from 0 and 1 has to be reachable from the nodes. All the other cycles might be usable in adding length to the k-path.

So for example, if there are cycles of lengths a, b and c then we can add any multiples of a, b or c to a valid length. Since the nodes we are considered are all correctly connected to 0 and 1, then paths exist contain nodes included in each of the 3 cycles. Take one of those paths and name its length L. Then we can add any multiples of a, b or c to that length and there will be valid paths of those lengths: L + ap + bq + cr, where p, q, r are non-negative integers. We need number theory to interpret this: Starting with L, all integers that are equal to L modulo a, b or c are valid. We need to find if the number of invalid integers is finite.

Here are a couple of ways to solve this question:

• You can ask yourself "What happens if a, b and c are all multiples of the same prime number p? Then no matter what you do, ap + bq + cr will always be a multiple of p. All gaps between L, L + p, L + 2p, L + 3p, … will be invalid.

• You can also use number theory knowledge to reach the same conclusion, in order for the number of invalid values not covered by L + ap + bq + cr to be infinite then gcd(a,b,c) != 1.

In general:

• If for any prime number p all possible cycle lengths are multiples of p , then the number of invalid k is infinite.

• OR

• If for any pair of existent cycle lengths (a,b), gcd(a,b) = 1, then the number of invalid k is finite.

Both views are equivalent.

Let’s use the former idea. Note that we can ignore non-simple cycles (cycles that include repeated nodes), because if all the simple cycles are multiples of p, then the non-simple cycles (Which are a sum of simple cycles) will also be multiples of p. This means that if the maximum simple cycle length is N, then we only need to consider values of p smaller than N+1. We can enumerate all primes up to 2000 and check.

A very nice approach to see if all cycles are multiples of p is to use a graph coloring: We have p colors numbered 0 to p-1. For any edge u -> v, the color of v should be equal to (“color of u” + 1) mod p. If this coloration is possible, then no simple cycle with length smaller than p exists. And all cycles with a larger or equal length to p have a length multiple of p.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// get all prime numbers up to N, return a list
list < int > get_primes(int N) {
  list < int > result;
  vector < bool > is_composite(N + 1, false);
  for (int p = 2; p <= N; p++) {
    if (!is_composite[p]) {
      result.push_back(p);
      for (int q = p + p; q <= N; q += p) {
        is_composite[q] = true;
      }
    }
  }
  return result;
}

// g: original directed graph, rg is the reverse.
vector < list < int >> g, rg;

// from_0[x] is true iif x is reachable from 0
// from_1[x] is true iif x is reachable from 1
// to_1[x] is true iif 1 is reachable from x
vector < bool > from_0, from_1, to_1;

// a BFS to get which nodes are reachable from/to 1/0:
void bfs(vector < list < int >> & g, int x, vector < bool > & visited) {
  queue < int > q;
  q.push(x);
  visited[x] = true;
  while (!q.empty()) {
    x = q.front();
    q.pop();
    for (int y: g[x]) {
      if (!visited[y]) {
        q.push(y);
        visited[y] = true;
      }
    }
  }
}

// The graph coloring, remember to ignore vertices not strongly connected to 0
vector < int > color;
bool color_dfs(int x, int p, int c) {
  if (!from_0[x] || !to_1[x]) {
    return true;
  }

  if (color[x] == -1) {
    color[x] = c;
    for (int y: g[x]) {
      if (!color_dfs(y, p, (c + 1) % p)) {
        return false;
      }
    }
  } else if (color[x] != c) {
    return false;
  }
  return true;
}

bool color_graph(int s, int p) {
  color.resize(g.size());
  fill(color.begin(), color.end(), -1);
  return color_dfs(s, p, 0);
}

string canWalkExactly(int N, vector < int > from, vector < int > to) {
  g.resize(N);
  rg.resize(N);
  for (int i = 0; i < from.size(); i++) {
    g[from[i]].push_back(to[i]);
    rg[to[i]].push_back(from[i]);
  }
  from_0.resize(N);
  from_1.resize(N);
  to_1.resize(N);
  bfs(g, 0, from_0);
  bfs(g, 1, from_1);
  bfs(rg, 1, to_1);

  if (!from_0[1] || !from_1[0]) {
    return "Chores";
  }

  // If for any prime p, we can do the coloring, return Chores:
  for (int p: get_primes(N + 1)) {
    if (color_graph(0, p)) {
      return "Chores";
    }
  }

  return "Freedom";
}

We can also enumerate all the simple cycles using a DFS (Depth-first search) and then check if the total gcd of all the cycle lengths is 1.

Brainstuck

The solution is going to be some kind of dynamic programming. Let’s count P(N) - the number of valid programs with exactly N characters. An important observation to make is that when exiting a loop, the memory cell will contain 0, so if the first non-nested loop ends with the m-th character, the number of choices for the last N-m characters is ans(N-m) regardless of what the first m were exactly.

We could try to count the number of programs which have only a single nested loop at the end and find a formula for the DP based on it, but let’s generalise and count the number of such programs which start with the value of the memory cell equal to c and exactly N characters - P_I(N,c). This can be used to compute P(N) using the formula (the last term is the number of programs without loops)

P(N)=\sum_m P_i(m,0)\cdot P(N-m)+2^N.

Before that non-nested loop, there are some +/- characters. We don’t care about them all that much, since if we define P_L(N,c) to be the number of subprograms executed within a loop that don’t run forever and start with memory cell = c, then P_I(N,c) can be computed by adding +/- in front of a loop, which gives a formula (the last term, again, is the number of programs without any +/- in front of the loop; we just take a nested subprogram and surround it with [/])

P_I(N,c)=P_I(N-1,c+1)+P_I(N-1,c-1)+P_L(N-2,c).

There is one special case: if c=0, then the loop in the last term isn’t executed at all and we should replace it by the number P_0(N-2) of correctly bracketed (but not necessarily terminating) programs, which can be counted with a simple DP.

Now to counting P_L. When does a nested subprogram exit the loop (which is a necessary condition for the whole program to terminate)? In other words, if it started with memory cell = c, what will that value be at the end? There are several options based on the structure of the subprogram.

If there is a loop inside it, then the memory cell will contain 0 after exiting it, so the final value is given by the number of +/- signs after it, regardless of the initial c. If the program exits, the numbers of + and - signs have to be equal. And before them, we can just stuff any valid program that doesn’t end with +/-; the number of such programs of length n is P(n)-2P(n-1). (Alternatively, we can take a valid subprogram of smaller length and stuff one of the programs counted in P_I() in front of it.)

If there are no loops, the difference between the numbers of + and - can be some non-zero number d. The value of the memory cell after this subprogram is ran once is c+d; there are again several cases depending on the signs of dand c:

• d=0: the memory cell remains = c, so it can only exit for c=0

• d > 0, c > 0: the value in the memory cell increases to infinity and it can never become zero, so it never exits the loop

• d > 0, c \le 0: the condition is that d divides -c - the program is ran (-c)/d times and then exits the loop

• d < 0: similar to d > 0 - it exits iff -d divides c \ge 0

So in order to count P_L(N,c), we need to add up two things. First, we try all values of d which lead to the program exiting, compute the numbers n_+ and n_- of + and - such that n_+ + n_- = N and n_+ - n_- = d, and add up the number of programs which consist of them - the binomial coefficient \frac{N!}{n_+! n_-!}. Second, we try all k \le N/2 and add up the number of programs ending with k pluses and k minuses, which is (P(N-2k)-2P(N-2k-1))\frac{(2k)!}{(k!)^2}.

This takes O(N^3) time, since we only need to consider |c| \le N - if c gets out of that range, the program can’t terminate anymore.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
vector < vector < long long > > C(N + 1, vector < long long > (N + 1, 0));
for (int i = 0; i <= N; i++) {
  C[i][0] = 1;
  for (int j = 1; j <= i; j++) {
    C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    if (C[i][j] >= M) C[i][j] -= M;
  }
}
vector < long long > pw(2 * N + 1, 1);
for (int i = 1; i <= 2 * N; i++) pw[i] = (2 * pw[i - 1]) % M;

vector < long long > P(N + 1, 0), P0(N + 1, 0);
vector < vector < long long > > Pi(N + 1, vector < long long > (2 * N + 1, 0));
auto Pl = Pi;
// P: number of programs (answer)
// Pl: number of programs with a single non-nested loop at the end
// Pi: number of programs which form a finite loop
// P0: number of ways to construct a program with matched brackets
P[0] = Pi[0][N] = P0[0] = 1;

for (int i = 1; i <= N; i++) {
  P0[i] = 2 * P0[i - 1];
  for (int j = 0; j <= i - 2; j++) P0[i] += (P0[i - 2 - j] * P0[j]) % M;
  P0[i] %= M;
  for (int j = 0; j <= 2 * N; j++) {
    if (j > 0) Pl[i][j] += Pl[i - 1][j - 1];
    if (j < 2 * N) Pl[i][j] += Pl[i - 1][j + 1];
    if (i >= 2) {
      if (j != N) Pl[i][j] += Pi[i - 2][j];
      else Pl[i][j] += P0[i - 2];
    }
    Pl[i][j] %= M;
  }
  for (int j = 0; j <= 2 * N; j++) {
    // no inner loops
    for (int k = 0; k <= i; k++) {
      if (2 * k - i == 0) {
        if (j != N) continue;
        Pi[i][j] += C[i][k];
        continue;
      }
      if (abs(N - j) % abs(2 * k - i) != 0) continue;
      int d = (N - j) / (2 * k - i);
      if (d > 0) Pi[i][j] += C[i][k];
    }
    // at least 1 inner loop
    for (int k = 2; k <= i; k++) Pi[i][j] += (Pl[k][j] * Pi[i - k][N]) % M;
    Pi[i][j] %= M;
  }
  P[i] = pw[i];
  for (int j = 2; j <= i; j++) P[i] += (Pl[j][N] * P[i - j]) % M;
  P[i] %= M;
}

if (P[N] < 0) P[N] += M;
return P[N];